package tree;

import java.util.Stack;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fc2sg/
public class 翻转二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //递归
    class Solution {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) return root;
            TreeNode tmp = root.left;
            root.left = mirrorTree(root.right);
            root.right= mirrorTree(tmp);
            return root;
        }
    }
    //辅助栈（或队列）
    class Solution2 {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) return null;
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()){
                TreeNode node = stack.pop();
                if(node.left != null) stack.add(node.left);
                if(node.right!= null) stack.add(node.right);
                TreeNode tmp = node.left;
                node.left = node.right;
                node.right= tmp;
            }
            return root;
        }
    }
}
